package com.sheng.leetcode.year2023.month08.day04;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/08/04
 * <p>
 * 62. 不同路径<p>
 * <p>
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。<p>
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。<p>
 * 问总共有多少条不同的路径？<p>
 * <p>
 * 示例 1：<p>
 * 输入：m = 3, n = 7<p>
 * 输出：28<p>
 * <p>
 * 示例 2：<p>
 * 输入：m = 3, n = 2<p>
 * 输出：3<p>
 * 解释：<p>
 * 从左上角开始，总共有 3 条路径可以到达右下角。<p>
 * 1. 向右 -> 向下 -> 向下<p>
 * 2. 向下 -> 向下 -> 向右<p>
 * 3. 向下 -> 向右 -> 向下<p>
 * <p>
 * 示例 3：<p>
 * 输入：m = 7, n = 3<p>
 * 输出：28<p>
 * <p>
 * 示例 4：<p>
 * 输入：m = 3, n = 3<p>
 * 输出：6<p>
 * <p>
 * 提示：<p>
 * 1 <= m, n <= 100<p>
 * 题目数据保证答案小于等于 2 * 10^9<p>
 */
public class LeetCode0062 {

    @Test
    public void test01() {
//        int m = 3, n = 7;
//        int m = 3, n = 2;
//        int m = 7, n = 3;
        int m = 3, n = 3;
        System.out.println(new Solution62().uniquePaths(m, n));
    }
}

class Solution62 {

    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        // 对于第一行，在边界，只能是 1
        for (int i = 0; i < m; i++) {
            f[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            f[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}
